package class41To50;

public class NMagicNumber {

    public static final int MOD = 1000000007;

    public int nthMagicalNumber(int n, int a, int b) {
        long lcm = (long) lcm(a, b);
        long l = 0;
        long r = (long) n * Math.min(a, b);
        long mid = 0;
        long ans = 0;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (mid / a + mid / b - mid / lcm >= n) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return (int) ans % MOD;
    }

    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
}
